简单讲讲布隆过滤器及其在HBase中的应用

1

什么是布隆过滤器

       布隆过滤器是一种多哈希函数映射的快速查找算法(存储结构），可以实现用很小的空间和运算代价，来实现海量数据的存在与否的记录（黑白名单判断）。特点是高效的插入和查询，可以判断出一定不存在和可能存在

      相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的可能存在结果是概率性的，而不是确切的。

布隆过滤器是一个bit向量或者bit数组

2

布隆过滤器操作及原理

1添加元素

        如果我们要添加一个值到布隆过滤器中，需要使用多个hash函数生成多个hash值，每个hash值对应位数组上的一个点，然后将位数组对应的位置标记为1。

      如下图，字符串'hello'就通过3种hash函数生成了哈希值1,3,9，字符串‘word’就生成了1,5,7

注：由于hello和word都返回了bit位1，所以前面的1会被覆盖

2查询元素

      查询元素flink是否存在集合中的时候，同样的方法将flink通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。

       如果3个点都为1，则该元素可能存在集合中。注意：此处不能判断该元素是否一定存在，可能存在一定的误判率。

      因为新增的元素越来越多，被置为 1 的 bit 位也会越来越多，这样“flink” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “flink” 这个值存在。比如flink三个hash值为1,3,7,就能说明flink一定存在吗?

3如何减少误差

• 加大布隆过滤器的长度，否则很容易就所有的bit位都为1了
  

• 哈希函数的个数要考虑，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误差会变高。

3

布隆过滤器在hbase中的应用

1布隆过滤器类型

       布隆过滤器是hbase中的高级功能，它能够减少特定访问模式（get/scan）下的查询时间。不过由于这种模式增加了内存和存储的负担，所以被默认为关闭状态。

hbase支持如下类型的布隆过滤器：

• NONE          不使用布隆过滤器

• ROW           行键使用布隆过滤器

• ROWCOL    列键使用布隆过滤器

至于选用什么模式，还是要看使用场景

2hbase数据存储及访问

        hbase的实际存储结构是HFile，它是位于hdfs系统中的，也就是在磁盘中。而加载到内存中的数据存储在MemStore中，当MemStore中的数据达到一定数量时，它会将数据存入HFile中。

       HFIle是由一个个数据块与索引块组成，他们通常默认为64KB。hbase是通过块索引来访问这些数据块的。而索引是由每个数据块的第一行数据的rowkey组成的。当hbase打开一个HFile时，块索引信息会优先加载到内存当中。然后hbase会通过这些块索引来查询数据。

3布隆过滤器在hbase中的应用

      当我们随机读get数据时，如果采用hbase的块索引机制，hbase会加载很多块文件。

       采用布隆过滤器后，它能够准确判断该HFile的所有数据块中是否含有我们查询的数据，从而大大减少不必要的块加载，增加吞吐，降低内存消耗，提高性能

         在读取数据时，hbase会首先在布隆过滤器中查询，根据布隆过滤器的结果，再在MemStore中查询，最后再在对应的HFile中查询。

如何写好一篇数据部门规范文档